package com.yulan.dp;

import org.junit.Test;

import java.util.Arrays;

/**
 * 279. 完全平方数
 */
public class LeetCode_279 {
    public int numSquares(int n) {
        int[] dp = new int[n+1];
        Arrays.fill(dp,Integer.MAX_VALUE);
        dp[0] = 0;
        //不可能超过这个数
        int maxIndex = (int)Math.sqrt(n)+1;

        int[] square_num = new int[maxIndex];
        //提前标记好平方数
        for(int i = 1;i<maxIndex;i++){
            square_num[i] = i * i;
        }

        for(int i = 1;i<=n ;i++){
            for(int start = 1;start < maxIndex;start++){
                if(i<square_num[start])//如果平方数比i要大 则说明不可能由该start组成
                    break;
                dp[i] = Math.min(dp[i],dp[i-square_num[start]]+1);
            }
        }
        return dp[n];
    }

    public  boolean isSquare(int n) {
        int sq = (int) Math.sqrt(n);
        return n == sq * sq;
    }


    public int numSquares2(int n){
        while ((n&3)==0)
            n /= 4;
        if((n&7)==7)
            return 4;

        if(isSquare(n))
            return 1;

        for(int i = 0; i*i <= n;i++){
            if(isSquare(n-i*i))
                return 2;
        }
        return 3;
    }

    @Test
    public void test(){
        System.out.println(numSquares(12));
    }
}
